package com.mgq.algorithm.twotree;

import java.util.HashMap;
import java.util.HashSet;

/**
 * 给定2个二叉树的node1和node2,找出他们的最低公共祖先
 * 如
 *              a
 *          b       c
 *       d    e        k
 *              f     g  h
 *              d和f的最低公共祖先是b
 *              f和e的最低公共祖先是e
 *              d和h的最低公共祖先是a
 *
 *最初汇聚的点就是公共祖先
 */
public class LowestCommonAncestor {


    /**
     * 方法一,使用hash表
     * d和f 记录d往上就是 d,b,a 加入set
     * f往上,找set中是否有,第一个有的节点就是他们的最低公共祖先
     * 先记录每个节点的父节点.然后把node1往上的节点全部加入到set
     * @param root
     * @param node1
     * @param node2
     */
    public TreeNode lca (TreeNode root,TreeNode node1,TreeNode node2) {
        HashMap<TreeNode, TreeNode> parentMap = new HashMap<>();
        parentMap.put(root, root);
        process(root,parentMap);
        HashSet<TreeNode> set = new HashSet<>();
        while (node1 != parentMap.get(root)) {
            set.add(node1);
            node1 = parentMap.get(node1);
        }
        while (node2 != parentMap.get(root)) {
            if (set.contains(parentMap.get(node2))) {
               return node2;
            }
            node2 = parentMap.get(node2);
        }
        return null;
    }

    public void process(TreeNode root, HashMap<TreeNode, TreeNode> fatherMap) {
        if (root == null) {
            return;
        }
        fatherMap.put(root.left, root);
        fatherMap.put(root.right, root);
        process(root.left,fatherMap);
        process(root.right,fatherMap);
    }

    /**
     * 方法二. 使用递归
     *              a
     *             /  \
     *            b    c
     *          /  \  / \
     *         e   f g   h
     * 第一种:O1是O2或者O2是O1的最低公共祖先
     *
     * 第二种:O1和O2不互为最低公共祖先,需要向上汇聚,此时当前节点是他们的祖先
     *
     *
     *
     * @param root
     * @param node1
     * @param node2
     * @return
     */
    public TreeNode lowestCommonAncestor (TreeNode root,TreeNode node1,TreeNode node2) {
       // base-case
        if (root == null || root == node1 || root == node2) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, node1, node2);
        TreeNode right = lowestCommonAncestor(root.left, node1, node2);
        //left和right都不空
        if (left != null && right != null) {
            return root;
        }
        //情况2.
        return left != null ? left : right;
    }
}
